package learn.letcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class ArrayStudy {

    public static int[] arrays = {0,1,2,3,4,5,6,7,8,9};

    /**
     * 暴力法
     * 寻找数组的中心下标(leetcode-724)
     * 给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。
     * 我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
     * 如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
     */
    public static int indexCenter(int[] nums){
        if (nums==null||nums.length<1){
            return -1;
        }
        for (int i=0;i<nums.length;i++){
            int left = 0;
            int right = 0;
            for (int j=0;j<i;j++){
                left += nums[j];
            }
            for (int j=i+1;j<nums.length;j++){
                right += nums[j];
            }
            if (left == right){
                return i;
            }
        }
        return -1;
    }

    /**
     * 寻找数组的中心下标(leetcode-724)
     * 记数组的全部元素之和为total，当遍历到第 i 个元素时，设其左侧元素之和为sum，则其右侧元素之和为total-nums[i]-sum
     * 当中心索引左侧或右侧没有元素时，即为零个项相加，这在数学上称作「空和」。在程序设计中我们约定「空和是零」。
     * @param nums
     * @return
     */
    public static int pivotIndex(int[] nums){
        if (nums==null||nums.length<1){
            return -1;
        }
        int total = Arrays.stream(nums).sum();
        int sum =0;
        for (int i=0;i<nums.length;i++){
            if (2*sum+nums[i]==total){
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }

    /**
     * 搜索插入位置(leetcode-35)
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
     * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 通过二分法查找
     * @return
     */
    public static int searchInsert(int[] nums,int target){
        int start=0;
        int end=nums.length-1;
        int ans=nums.length;
        while (start<=end){
           int middle = (start + end)/2;
           if (target<=nums[middle]){
               ans = middle;
               end = middle-1;
           }else{
               start = middle+1;
           }
        }
        return ans;
    }


    /**
     * 合并区间((leetcode-56))
     * 我们用数组 merged 存储最终的答案。
     *
     * 首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
     * 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
     * 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
     *
     * @param arrays
     * @return
     */
    public static int[][] merge(int[][] arrays){
        if (arrays.length==0){
            return new int[0][2];
        }
        Arrays.sort(arrays, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        //一维数组转二维数组
        List<int[]> mergeList = new ArrayList<>();
        for (int i=0;i<arrays.length;i++){
            int l = arrays[i][0];
            int r = arrays[i][1];
            if (mergeList.size()==0 || mergeList.get(mergeList.size()-1)[1]<l){
                mergeList.add(new int[]{l,r});
            }else{
                mergeList.get(mergeList.size()-1)[1] = Math.max(mergeList.get(mergeList.size()-1)[1],r);
            }
        }

        return  mergeList.toArray(new int[mergeList.size()][0]);
    }

    /**
     * 旋转矩阵
     * 对于矩阵中的第三行和第四行同理。这样我们可以得到规律：
     * 对于矩阵中第 ii 行的第 jj 个元素，在旋转后，它出现在倒数第 ii 列的第 jj 个位置。
     * 我们将其翻译成代码。由于矩阵中的行列从 00 开始计数，因此对于矩阵中的元素
     * matrix_new[col][n−row−1]=matrix[row][col]
     *
     * @param matrix
     * @return
     */
    public static int[][] rotate(int[][] matrix){
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];

        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                matrix_new[j][n-i-1] = matrix[i][j];
            }
        }

        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                matrix[i][j] = matrix_new[i][j];
            }
        }
        return matrix;
    }

    /**
     * 矩阵置0(leetcode-73)
     * 我们可以用两个标记数组分别记录每一行和每一列是否有零出现。
     * 具体地，我们首先遍历该数组一次，如果某个元素为 00，那么就将该元素所在的行和列所对应标记数组的位置置为true。最后我们再次遍历该数组，用标记数组更新原数组即可。
     * @param matrix
     * @return
     */
    public static int[][] setZeroes(int[][] matrix){
        int m = matrix.length;
        int n = matrix[0].length;

        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];

        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (matrix[i][j]==0){
                    row[i] = col[j] = true;
                }
            }
        }

        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (row[i]||col[j]){
                    matrix[i][j]=0;
                }
            }
        }

        return matrix;

    }



    public static void main(String[] args) {
        int[] array = {1, 7, 3,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9, 6, 5, 6,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9};

        long start = System.currentTimeMillis();
        System.out.println(indexCenter(array));
        long end = System.currentTimeMillis();
        System.out.println("indexCenter:"+(end-start));

        long start1 = System.currentTimeMillis();
        System.out.println(pivotIndex(array));
        long end1 = System.currentTimeMillis();
        System.out.println("pivotIndex:"+(end1-start1));

        int[] searchAr = {1,3,5,6};
        System.out.println(searchInsert(searchAr,7));

        int[][] merge = {{1,3},{2,6},{5,7},{8,10},{12,18}};
        int[][] merge1 = merge(merge);
        System.out.println(Arrays.deepToString(merge1));

        int[][] rotate = {{1,2,3},{4,5,6},{7,8,9}};
        int[][] rotate1 = rotate(rotate);
        System.out.println(Arrays.deepToString(rotate1));

        int[][] setZeros = {{1,2,3},{4,0,0},{7,8,9}};
        int[][] ints = setZeroes(setZeros);
        System.out.println(Arrays.deepToString(ints));
    }
}
